package com.dragon.datastructure.sort;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author dragon
 * @since 2019/12/25
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] array = {11, 1, 2, 3, 4, 5, 12, 13, 15};

        sort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 快速排序
     *
     * @param array 需要排序的数组
     * @param left  左边索引
     * @param right 右边索引
     */
    public static void sort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int l = left;
        int r = right;
        // 将数组最左边的数看作基准数
        int base = array[l];
        while (l != r) {
            // 先从right角标开始从后往前查找看是否有元素是小于基准数的，如果小于，则停住
            while (l < r && array[r] >= base) {
                // 如果说数组右边查找到的数是大于或者等于基准数的，则角标往后移动
                r--;
            }
            // 在从left角标开始从前往后查找看是否有元素是大于基准数的，如果大于，则停住
            while (l < r && array[l] <= base) {
                // 如果说能够进来，说明查找的元素的值是小于等于基准数的是，则角标往前移动
                l++;
            }
            // 因为有可能只要一次，左边索引与右边索引就相遇了，所以就不需要执行下面的交换，这是一种极端的情况
            if (l == r) {
                break;
            }
            // 交换位置
            int temp = array[l];
            array[l] = array[r];
            array[r] = temp;
        }
        // 执行到这里，就说明 l == r ，说明已经找到了一个角标，他的左边都是小于等于该角标的值，它的右边都是大于等于该角标的值
        array[left] = array[l];
        array[l] = base;

        sort(array, left, l - 1);
        sort(array, l + 1, right);
    }

}
